from pyproj import Transformer
import csv

def test(d):
    coordinateTask=[]
    coordinateWorker=[]
    transformer = Transformer.from_crs(crs_from="EPSG:4326",crs_to="EPSG:4087")#将GPS坐标转化为平面坐标
    fileNameTask = "demand_2016.08."+d[0]+"_610100_.csv"
    fileNameWorker = "distribute_2016.08."+d[0]+"_610100_.csv"
    with open(file=fileNameTask,mode='r',encoding='utf-8') as f:
            fdata = csv.reader(f)
            next(fdata)
            for i in fdata:
                hour = float(i[1])
                longitude = float(i[2])
                latitude = float(i[3])
                tr = transformer.transform(latitude,longitude)
                # coordinateTask.append(tr)
                coordinateTask.append([tr[0],tr[1]])
    with open(file=fileNameWorker,mode='r',encoding='utf-8') as f:
        fdata = csv.reader(f)
        next(fdata)
        for i in fdata:
            hour = float(i[1])
            longitude = float(i[2])
            latitude = float(i[3])
            tr = transformer.transform(latitude,longitude)
            # coordinateWorker.append(tr)
            coordinateWorker.append([tr[0],tr[1]])

    with open("../testdata2.txt",mode='w',encoding='utf-8') as f:
        workerNum = len(coordinateWorker)
        taskNum = len(coordinateTask)
        sumNum = workerNum+taskNum
        f.write(str(workerNum)+" "+str(taskNum)+" "+str(sumNum)+"\n")
        for longitude,latitude in coordinateTask:
            wstr = "t "+str(longitude)+" "+str(latitude)
            f.write(wstr+"\n")
        for longitude,latitude in coordinateWorker:
            wstr = "w "+str(longitude)+" "+str(latitude)+" 1000"
            f.write(wstr+"\n")

if __name__ =="__main__":
    # read()
    # day = ["06","07","08","09","10","11","12"]
    day = ["12"]

    test(day)


INF = float('inf')

def KM_algorithm(graph):
    """
    使用KM算法解决二分图的最大权匹配问题
    :param graph: 二分图的邻接矩阵表示
    :return: 最大权匹配的权重和
    """
    n = len(graph)
    match = [-1] * n  # 存储最大匹配的结果，match[i]表示左侧顶点i匹配的右侧顶点编号
    lx = [-INF] * n  # 左侧顶点的标号
    ly = [0] * n  # 右侧顶点的标号
    slack = [INF] * n  # 松弛数组，表示在增广路径上未被选中的右侧顶点的最小标号差值
    visx = [False] * n  # 左侧顶点的访问状态
    visy = [False] * n  # 右侧顶点的访问状态

    def dfs(x):
        visx[x] = True
        for y in range(n):
            if visy[y]:
                continue
            gap = lx[x] + ly[y] - graph[x][y]
            if gap == 0:
                visy[y] = True
                if match[y] == -1 or dfs(match[y]):
                    match[y] = x
                    return True
            else:
                slack[y] = min(slack[y], gap)
        return False

    # 初始化左侧顶点的标号
    for i in range(n):
        for j in range(n):
            lx[i] = max(lx[i], graph[i][j])

    # 匈牙利算法主循环
    for x in range(n):
        while True:
            # 初始化访问状态和松弛数组
            visx = [False] * n
            visy = [False] * n
            slack = [INF] * n
            if dfs(x):
                break

            # 如果找不到增广路径，则需要调整标号以使图中边的权重更小
            d = INF
            for i in range(n):
                if not visy[i]:
                    d = min(d, slack[i])
            if d == INF:
                return sum(lx) + sum(ly)
            
            for i in range(n):
                if visx[i]:
                    lx[i] -= d
                if visy[i]:
                    ly[i] += d

    return sum(lx) + sum(ly)